﻿#pragma once
#include "Index.h"

class ISearchA2DMatrixII
{
public:
	/**
	 * 搜索二维矩阵II.
	 * 数组 二分 分治 矩阵
	 * https://leetcode.cn/problems/search-a-2d-matrix-ii/
	 *
	 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     * 每行的元素从左到右升序排列。
     * 每列的元素从上到下升序排列。
	 */
	virtual bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) = 0;
};

class SearchA2DMatrixII
{
public:
	class Binary:public ISearchA2DMatrixII
	{
	public:
		bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) override
		{
			if (matrix.empty() || matrix.front().empty())
				return false;

			const int rowSize = matrix.size();
			const int colSize = matrix.front().size();

			int row=0,col = colSize - 1;
			while (row < rowSize && col>=0)
			{
				if (matrix[row][col] == target)
					return true;
				else if (matrix[row][col] < target)
					row++;
				else
					col--;
			}
			return false;
		}
	};
};
